package com.jxb.four;

import java.util.Stack;

/**每日温度
 输入: temperatures = [73,74,75,71,69,72,76,73]
 输出:    [1,1,4,2,1,1,0,0]

 思路：
    1：通过栈来实现
    2：通过倒叙暴力穷举来实现，过滤掉重复步骤
 ** @author jiaobo
 * @date Created in 2024/12/30 20:07
 **/
public class DailyTemperatures_739 {

    public static void main(String[] args) {
        int[] arr = {73,74,75,71,69,72,76,73};
        int[] ints = dailyTemperBaoli(arr);
        System.out.println("--");
    }

    //通过栈来实现
    public static int[] dailyTemper(int[] nums) {
        //出参
        int[] resArr = new int[nums.length];
        //定义一个栈(存入的是元素坐标)
        Stack<Integer> stack = new Stack<>();
        stack.push(0);
        for (int i = 1;i<nums.length;i++) {
            while (!stack.isEmpty() && nums[stack.peek()] < nums[i]) {
                int s = stack.pop();
                resArr[s] = i - s;
            }
            stack.push(i);
        }
        return resArr;
    }

    //暴力穷举
    public static int[] dailyTemperBaoli(int[] nums) {
        int[] resArr = new int[nums.length];
        int n = nums.length - 2;
        //倒序遍历
        for (int i = n;i>=0;i--) {
            for (int backIdx = i+1;backIdx < nums.length;backIdx = backIdx + resArr[backIdx] ) {
                if (nums[backIdx] > nums[i]) {
                    resArr[i] = backIdx - i;
                    break;
                } else if (resArr[backIdx] == 0) {
                    resArr[i] = 0;
                    break;
                }
            }
        }
        return resArr;
    }

}
